1. Field of Invention
The present invention generally concerns a method and apparatus for buffering data within stations of a communications network, and more particularly to such a method and apparatus which enables each station to receive and transmit consecutive data packets in a manner less sensitive to processor interrupt latency, while optimally using memory and minimizing host processor overhead and necessity of copying data between structures.
2. Brief Description of the Prior Art
Local-area networks (LAN) are communication systems for enabling data-processing devices, such as computer workstations, to communicate with each other through a communication (e.g. transmission) media. Data-processing devices in such networks are typically referred to as nodes or stations, and many such stations are likely to be relatively autonomous, requiring communication with other stations only occasionally. Other stations may require more frequent communication, and the amount of communication required by a particular station can vary from time to time.
In many local area networks, stations can be easily added to, removed from, and moved from place to plate within the network. While there are numerous local area networks presently known, they can be classified into two general types. The first type of network is referred to as a "centralized network" which is characterized by the requirement of a centralized network controller which implements the network protocol. The second type of local area network is referred to as a "distributed network" which does not require a centralized network controller, and instead provides each station within the network with a communication controller having a medium access control (MAC) unit that locally implements the network protocol within each communication controller.
In a distributed local area network, packet switching is a technique commonly employed to dynamically allocate the communication resources of the network among multiple communicating stations. According to this technique, messages to be communicated between stations are partitioned (by the transmitting station's processor) into packets, having a fixed maximum size. The packets are then ascribed a station (i.e. source) identifier. The packets are then placed on the communication medium by the station's communication controller. Such packets are then sensed and selectively processed by the communication controller of the destination station in the network.
Any packet from one station to another station contains various fields of information specified in accordance with a predetermined network protocol. The information typically includes the identity of the source station, the identity of the destination station, and various other information concerning the characteristics of the packet. In some network protocols, a number of different types of packets may appear on the communication medium in accordance with the network protocol. Typically, these packets relate to either communication control or data-transfer functions.
To more fully appreciate the problems associated with conventional communication controllers used in the stations of distributed local-area-networks, reference is made to FIGS. 1 through 3.
In FIG. 1, a distributed local area-network 100 is shown, comprising a plurality of stations (i.e. nodes 102A through 102M) which are operably associated to a communication medium 103, such as a cable. In FIG. 2, each station is shown to generally comprise a host processor (e.g., CPU) 104, a program memory 105, a system memory 106, a communication controller 107, a system bus 108, and a communication medium interface unit 109. The processor, program memory and system memory are each associated with a system bus 108, and the system bus, in turn, is interfaced with communication controller 107, as shown. The communication controller is interfaced with the communication medium by way of the communication medium interface unit. Typically, the communication medium interface unit is suitably adapted for the particular characteristics of the communication medium being employed in the network.
In general, communication controllers, and LAN controllers in particular, are usually integrated into a system architecture and software environment by providing the means for supporting two independent data queues in software: a transmit queue and a receive queue. Each queue is associated with a process, namely, the transmit process and the receive process of the low-level software communications driver.
The transmit queue holds the elements that the software intends to transmit. In a packet-switched environment of a local area network, these elements are usually data packets that include a block of data to be transmitted and some associated information like the destination for the block of data. The receive queue hold the elements that the station has received, again usually packets with a block of data and associated information such as the sender of the data block.
Elements are added to the transmit queue by the software driver whenever it needs to transmit information. Elements are removed from the transmit queue after successful transmission is assumed. Removal of the elements can be done either by the low-level software driver or by the communication controller. Elements are added to the receive queue by the communication controller whenever a relevant packet is received, and are removed by the low-level software driver upon processing the packet.
The transmit and receive queues are managed by software in system memory, and eventually meet the communication controller. The interface between the queues and the communications controller determines the behavior of the queues during the addition of receive elements and removal of transmit elements.
Management of the transmit and receive queue elements at the level of the communication controller has been attempted in a variety of ways.
For example, some prior art communication controllers are as simple as a single element queue, in which the controller can handle only one transmit and one receive element at a time and the host processor must be involved in feeding the queue. Representative of this type of prior art is the 90C65 Communication Controller from Standard Microsystems Corporation of Hauppauge, N.Y. A major shortcoming of this type of communication controller is that it is highly sensitive to interrupt latency of the host processor.
An alternative type of prior art communication controller employs queues for transmit and receive commands while storing corresponding data packets in a randomly accessible memory associated with the communication controller. Representative of this type of prior art is the 90C66 Communication Controller from Standard Microsystems. Advantageously, this communication controller design is substantially less sensitive to interrupt latency in comparison with the above-described communication controller.
Using an altogether different technique than the command queuing scheme described above, the prior art has sought to extend the transmit and receive data queues into the communication controller by simulating transmit and receive data queues in the data packet buffer memory of the communication controller. In general, there have been several different approaches to implementing this generalized memory management technique.
For example, according to one approach, many transmit and receive data elements can be managed as a "ring buffer," in which data packet buffer memory is configured as a number of memory elements which can be sequentially allocated and accessed. Prior art representative of this approach includes the 8390 NIC Communication Controller from National Semiconductor Corporation, and the Etherstar.RTM. Ethernet Communications Controller from Fujitsu Corporation. Significant shortcomings and drawbacks of the "ring buffer" communication controller are inefficient memory utilization, high CPU overhead and memory fragmentation.
According to an alternative approach for simulating transmit and receive data queues at the communication controller level, a disjointed array of memory storage locations are linked together with the use of address pointers compiled in accordance with a "linked list". The major subcomponents of such a conventional "link-list" communication controller 107' are shown in FIG. 3. In general, communication controller 107' comprises a CPU interface unit 110, a link-list processor 111, a medium access control (MAC) unit 112, and a MAC interface unit 114. Associated with the controller is a data packet buffer memory (RAM) 113. The CPU interface unit interfaces system bus 108 with the link-list processor and the data packet memory buffer by way of an address and data bus, as shown. The MAC interface unit interfaces the medium access control unit 109 with the link-list processor and the data packet buffer memory, also by way of an address and data bus, as shown. Prior art representative of the above type device includes the 82586 and 82596 Communication Controllers from Intel Corporation.
In order for the link-list communication controller to find the memory storage location where a packet begins, as well as the storage locations where each one of the buffers (comprising a packet) begins, the software driver must perform a number of computations. Such packet address computations and the necessity of managing numerous address pointers create high software overhead. Also with this prior art approach, memory utilization is inefficient owing to the fact that pointers and link-list structures utilize memory and due to the fact that link-lists use fixed memory allocations between transmit and receive queues.
Thus, there is a great need in the art for a communication controller that can efficiently manage its data packet buffer memory and interface with transmit and receive queues in system memory, while buffering data packets in a manner which is characterized by simplicity, high performance, flexibility, low software overhead, and efficient memory utilization.
Accordingly, it is a primary object of the present invention to provide a method and apparatus for buffering data packets in a communication controller in a way which generally satisfies the above-described criteria.
It is a further object of the present invention to provide such a method and apparatus of buffering data packets in a communication controller, in a way which transmit and receive data queues can be managed independently of the host processor (CPU), and insensitive to its interrupt latency time.
It is a further object of the present invention to provide such a method and apparatus of buffering data packets in a communication controller, in which data packet buffer memory is dynamically allocated so as to optimize memory utilization without burden on the host processor.
A further object of the present invention is to provide such a method and apparatus of buffering data packets in a communication controller in which data packet buffer memory appears to the host processor as two linearly mapped fixed-length regions of memory space for the transmit and receive queues, respectively, while in actuality, the size of the buffer memory is much greater, and the data page storage locations for each data packet are arbitrarily assigned, need not be contiguous, and number thereof is dependent on the actual length of the data packet to be stored.
A further object of the present invention is to provide such method and apparatus in the form of a communication controller, in which buffer memory space between transmit and receive data packet queues is shared and dynamically allocated to optimize memory utilization.
A further object of the present invention is to provide such a communication controller, in which dynamic allocation of buffer memory is transparent to the host processor and the medium access control unit of the communication controller.
These and other objects of the present invention will become apparent hereinafter.